package com.breeze.xiangxue.linkedlist;

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
        // 4.如何得到单链表的长度? 360
        // 1->2->3->4
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        System.out.println("==========题4===========");
        System.out.println(getSingleLinkedListLength(head));
        // 5. 如何在不使用递归的情况下逆转单链表? 小米/美团/快手
        reverseSingleLinkedList(head);
        System.out.println("==========题6===========");
        showLinkedList(head);
        System.out.println();
        System.out.println(getMiddleNode(head).value);
        // 7. 如何证明给定的链表是否包含循环?如何找到循环的头节点? 优酷 腾讯 滴滴
        System.out.println("==========题7===========");
        System.out.println(hasCycle(head));
        // 1->2->3->4->5
        //       ^------
        Node head1 = new Node(1);
        Node head2 = new Node(2);
        Node head3 = new Node(3);
        Node head4 = new Node(4);
        Node head5 = new Node(5);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head3;
        System.out.println(hasCycle(head1));
        System.out.println(getCycleHead3(head1).value);
        System.out.println("==========题8===========");
        Node headA = new Node(1);
        headA.next = new Node(2);
        Node headB = new Node(11);
        headB.next = new Node(12);
        Node intersection = new Node(100);
        intersection.next = new Node(101);
        headA.next.next = intersection;
        headB.next.next = intersection;
        System.out.println(getIntersectionNode(headA, headB).value);
        System.out.println(getIntersectionNode2(headA, headB).value);
        showLinkedList(headA);
        showLinkedList(headB);
    }

    /**
     * 4. 如何得到单链表的长度? 360
     * https://blog.csdn.net/weixin_41924879/article/details/100065838
     */
    public static int getSingleLinkedListLength(Node head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    /**
     * 5. 如何在不使用递归的情况下逆转单链表? 小米/美团/快手
     * https://blog.csdn.net/shine0312/article/details/87938865
     */
    public static void reverseSingleLinkedList(Node head) {
        // TODO:
    }

    /**
     * 6. 如何在一次遍历中找到单个链表的中间节点的值? 中国平安
     * https://blog.csdn.net/skyejy/article/details/100112481
     */
    public static Node getMiddleNode(Node head) {
        // 快慢指针
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }
        return slow;
    }

    /**
     * 7. 如何证明给定的链表是否包含循环?如何找到循环的头节点? 优酷 腾讯 滴滴
     * https://blog.csdn.net/yangruxi/article/details/80333000
     * 见LeetCode142
     * 哈希表方法
     */
    public static Node getCycleHead1(Node head) {
        Set<Node> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

    // 7 题，方法二
    public static Node getCycleHead2(Node head) {
        // 龟兔起跑
        Node slow = head;
        Node fast = head;
        Node meet = null;
        while (slow != null && fast != null && fast.next != null) {
            // 龟走一步
            slow = slow.next;
            // 兔走两步
            fast = fast.next.next;
            // 两者只要相遇即为环，当然相遇不一定是环的起点
            if (slow == fast) {
                meet = slow;
                break;
            }
        }
        if (meet == null) {
            return null;
        }
        // 得出圆长
        int count = 1;
        Node start = meet.next;
        while (start != meet) {
            count++;
            start = start.next;
        }
        // begin 节点行走圆长
        Node begin = head;
        for (int i = 0; i < count; i++) {
            begin = begin.next;
        }
        // begin 节点和head 同时行走，相遇即为开始节点
        while (true) {
            if (begin == head) {
                return begin;
            }
            head = head.next;
            begin = begin.next;
        }
    }

    // 7 题 方法3
    public static Node getCycleHead3(Node head) {
        Node fast = head, slow = head;
        while (true) {
            // 无环
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            // 相遇即存在环
            if (fast == slow) {
                break;
            }
        }
        // fast 站在头节点，slow依然在nb的位置，两人起步走，相遇即为环头
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static boolean hasCycle(Node head) {
        // 快慢指针，如果相遇则存在循环
        if (head == null && head.next == null) {
            return false;
        }
        Node slow = head;
        Node fast = head.next;
        while (fast != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        return false;
    }

    /**
     * 8. 两个有交叉的单链表,求交叉点 华为
     * https://blog.csdn.net/u011046509/article/details/80918952
     * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
     * 方法一：暴力法
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     */
    public static Node getIntersectionNode(Node headA, Node headB) {
        Node node = headB;
        while (headA != null) {
            while (node != null) {
                if (node == headA) {
                    return node;
                }
                node = node.next;
            }
            headA = headA.next;
            node = headB;
        }
        return null;
    }

    /**
     * 8题 方法二
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static Node getIntersectionNode2(Node headA, Node headB) {
        if (headA == null || headB == null) return null;
        Node pA = headA;
        Node pB = headB;
        // 当两个链表不相交时，会因为pA和pB都为null而退出循环
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * 9题 合并单链表 字节跳动/美团   见LeetCode21
     */

    /**
     * 10题 如何找链表倒数第n个元素？快慢指针 腾讯  见Offer22
     */

    /**
     * 11题 求矩阵中连续1的个数 Number of Islands 三星 见LeetCode1254（待完成）
     */

    /**
     * 12 题 大数相加(今日头条，美团) 见LeetCode2和LeetCode445(待完成)
     */


    /**
     * 遍历链表
     */
    public static void showLinkedList(Node head) {
        while (head != null) {
            System.out.print(head.value + ",");
            head = head.next;
        }
    }

    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}
